package main.leetcode.offer.firstround.from03to50;

import java.util.HashMap;

/**
 * 35.复杂链表的复制
 *
 * <p>请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者
 * null。
 *
 * <p>
 *
 * <p>示例 1：输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 *
 * <p>示例 2：输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]
 *
 * <p>示例 3：输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
 *
 * <p>示例 4：输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
 *
 * <p>提示：-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex35 {

    // 回溯
    private HashMap<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (map.containsKey(head)) return map.get(head);
        Node node = new Node(head.val);
        map.put(head, node);
        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);
        return node;
    }

    // O(1) 空间的迭代
    public Node copyRandomList1(Node head) {
        if (head == null) return null;
        Node pre = head;
        Node node;
        while (pre != null) {
            node = new Node(pre.val);
            node.next = pre.next;
            pre.next = node;
            pre = node.next;
        }
        pre = head;
        while (pre != null) {
            node = pre.next;
            node.random = pre.random == null ? null : pre.random.next;
            pre = node.next;
        }
        pre = head;
        node = head.next;
        Node newHead = node;
        while (pre != null) {
            pre.next = node.next;
            node.next = node.next == null ? null : node.next.next;
            pre = pre.next;
            node = node.next;
        }
        return newHead;
    }

    /** Definition for a Node. */
    class Node {
        int val;
        Node next;
        Node random;

        Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
